package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/validate-stack-sequences/
 * @create 2025/9/8 18:47
 * @since JDK17
 */

public class Solution59 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length, top = 0, i, j;
        int[] stack = new int[n];
        for (i = j = 0; j < n; ) {
            while (i < n && (top == 0 || stack[top - 1] != popped[j])) {
                stack[top++] = pushed[i++];
            }
            if (i == n && stack[top - 1] != popped[j]) {
                return false;
            }
            if (stack[top - 1] == popped[j]) {  //
                top--;
                j++;
            }
        }

        return true;
    }
}
